
/*
回溯
连接：https://leetcode.cn/problems/combinations/description/
题目：77. 组合


    3. 解法（回溯）：
    算法思路：
    题⽬要求我们从 1 到 n 中选择 k 个数的所有组合，其中不考虑顺序。也就是说，[1,2] 和 [2,1] 等价。我
    们需要找出所有的组合，但不能重复计算相同元素的不同顺序的组合。对于选择组合，我们需要进⾏
    如下流程：
    1. 所有元素分别作为⾸位元素进⾏处理；
    2. 在之后的位置上同理，选择所有元素分别作为当前位置元素进⾏处理；
    3. 为避免计算重复组合，规定选择之后位置的元素时必须⽐前⼀个元素⼤，这样就不会有重复的组合
    （[1,2] 和 [2,1] 中 [2,1] 不会出现）。
    递归函数设计：void dfs(vector<vector<int>>& ans, vector<int>& v, int step, int &n, int &k)
    参数：step（当前需要进⾏处理的位置）；
    返回值：⽆；
    函数作⽤：某个元素作为⾸位元素出现时，查找所有可能的组合。
    具体实现⽅法如下：
    1. 定义⼀个⼆维数组和⼀维数组。⼆维数组⽤来记录所有组合，⼀维数组⽤来记录当前状态下的组
    合。
    2. 遍历 1 到 n-k+1，以当前数作为组合的⾸位元素进⾏递归（从 n-k+1 到 n 作为⾸位元素时，组合中
    ⼀定不会存在 k 个元素）。
    3. 递归函数的参数为两个数组、当前步骤以及 n 和 k。递归流程如下：
    a. 结束条件：当前组合中已经有 k 个元素，将当前组合存进⼆维数组并返回。
    ▪ 剪枝：如果当前位置之后的所有元素放⼊组合也不能满⾜组合中存在 k 个元素，直接返回。
    b. 从当前位置的下⼀个元素开始遍历到 n，将元素赋值到当前位置，递归下⼀个位置。

*/
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int k_num;
    int n_num;
    vector<vector<int>> combine(int n, int k) {
        k_num =k;
        n_num =n;
        dfs(0,1);
        return ret;
    }
    void dfs(int num,int pos)
    {
        if(num==k_num)
        {
            ret.push_back(path);
            return;
        }
        for(int i=pos;i<=n_num;i++)
        {
            path.push_back(i);
            dfs(num+1,i+1);
            path.pop_back();
        }
    }
};